package nowCoder;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * Created by Ghost on 2015/2/18.
 *有一个链表，其中每个对象包含两个指针p1, p2，其中指针p1指向下一个对象，指针p2也指向一个对象，沿p1可以像普通链表一样完成顺序遍历，沿p2则可能会有重复。 一种可能的例子如下，其中实线箭头是p1, 虚线箭头是p2：

 问题：设计函数，翻转这个链表，并返回头指针。链表节点的数据结构如下：
 */
class Node{
    Node p1,p2;
    int data;
}
public class Reverse_List {
    HashMap<Node, Node> hashMap = new HashMap<Node, Node>();
    public void reverse(Node head){
        Node pre = head;
        Node cur = head.p1;
        Node realTail = cur;
        while(cur!=null){
            Node next = cur.p1;
            cur.p1 = pre;
            pre = cur;

            if(cur.p2!=null)
                hashMap.put(cur,cur.p2);

            cur = next;

        }
        head.p1 = pre;
        realTail.p1 = null;
        Set<Map.Entry<Node, Node>> entry = hashMap.entrySet();
        for(Map.Entry<Node, Node> entry1:entry){
            Node a = entry1.getKey();
            Node b = entry1.getValue();
            b.p2 = a;
        }
    }
}
